package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC973 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int[][] kClosest(int[][] points, int K) {
            Map<Long, List<int[]>> countMap = new TreeMap<>();
            for (int[] point : points) {
                long distance = point[0] * point[0] + point[1] * point[1];
                if (countMap.containsKey(distance)) countMap.get(distance).add(point);
                else {
                    List<int[]> list = new ArrayList<>();
                    list.add(point);
                    countMap.put(distance, list);
                }
            }

            int[][] res = new int[K][2];
            int count = 0;
            for (List<int[]> pointList : countMap.values()) {
                for (int[] point : pointList) {
                    res[count++] = point;
                    if (count == K) return res;
                }
            }

            return res;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[][] arr = InputUtil.toDoubleIntegerArray("[[3,3],[5,-1],[-2,4]]");
        System.out.println(Arrays.toString(solution.kClosest(arr, 2)));
    }

    public static void main(String[] args) throws Exception {
        LC973 an = new LC973();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
